<!DOCTYPE html>
<html lang="zh-cn">
    <head><meta charset='utf-8'>
<meta name='viewport' content='width=device-width, initial-scale=1'><meta name='description' content='考前整理的数据结构算法'><title>数据结构算法复习</title>

<link rel='canonical' href='https://luobo.cf/p/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95%E5%A4%8D%E4%B9%A0/'>

<link rel="stylesheet" href="/scss/style.min.css"><meta property='og:title' content='数据结构算法复习'>
<meta property='og:description' content='考前整理的数据结构算法'>
<meta property='og:url' content='https://luobo.cf/p/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95%E5%A4%8D%E4%B9%A0/'>
<meta property='og:site_name' content='luoboQAQ'>
<meta property='og:type' content='article'><meta property='article:section' content='Post' /><meta property='article:tag' content='C' /><meta property='article:published_time' content='2021-01-10T15:06:20&#43;08:00'/><meta property='article:modified_time' content='2021-01-13T20:47:14&#43;08:00'/><meta property='og:image' content='https://luobo.cf/p/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95%E5%A4%8D%E4%B9%A0/83667969.png' />
<meta name="twitter:title" content="数据结构算法复习">
<meta name="twitter:description" content="考前整理的数据结构算法"><meta name="twitter:card" content="summary_large_image">
    <meta name="twitter:image" content='https://luobo.cf/p/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95%E5%A4%8D%E4%B9%A0/83667969.png' />
    </head>
    <body class="
    article-page has-toc
">
    <script>
        (function() {
            const colorSchemeKey = 'StackColorScheme';
            if(!localStorage.getItem(colorSchemeKey)){
                localStorage.setItem(colorSchemeKey, "auto");
            }
        })();
    </script><script>
    (function() {
        const colorSchemeKey = 'StackColorScheme';
        const colorSchemeItem = localStorage.getItem(colorSchemeKey);
        const supportDarkMode = window.matchMedia('(prefers-color-scheme: dark)').matches === true;

        if (colorSchemeItem == 'dark' || colorSchemeItem === 'auto' && supportDarkMode) {
            

            document.documentElement.dataset.scheme = 'dark';
        } else {
            document.documentElement.dataset.scheme = 'light';
        }
    })();
</script>
<div class="container main-container flex 
    
        extended
    
">
    
        <div id="article-toolbar">
            <a href="https://luobo.cf" class="back-home">
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-chevron-left" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <polyline points="15 6 9 12 15 18" />
</svg>



                <span>返回</span>
            </a>
        </div>
    
<main class="main full-width">
    <article class="has-image main-article">
    <header class="article-header">
        <div class="article-image">
            <a href="/p/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95%E5%A4%8D%E4%B9%A0/">
                <img src="/p/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95%E5%A4%8D%E4%B9%A0/83667969_hu38d2b1a912e76eab4c1b90daa958e1cd_1812230_800x0_resize_box_3.png"
                        srcset="/p/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95%E5%A4%8D%E4%B9%A0/83667969_hu38d2b1a912e76eab4c1b90daa958e1cd_1812230_800x0_resize_box_3.png 800w, /p/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95%E5%A4%8D%E4%B9%A0/83667969_hu38d2b1a912e76eab4c1b90daa958e1cd_1812230_1600x0_resize_box_3.png 1600w"
                        width="800" 
                        height="600" 
                        loading="lazy"
                        alt="Featured image of post 数据结构算法复习" />
                
            </a>
        </div>
    

    <div class="article-details">
    

    <h2 class="article-title">
        <a href="/p/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95%E5%A4%8D%E4%B9%A0/">数据结构算法复习</a>
    </h2>

    
    <h3 class="article-subtitle">
        考前整理的数据结构算法
    </h3>
    

    
    <footer class="article-time">
        
            <div>
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-calendar-time" width="56" height="56" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <path d="M11.795 21h-6.795a2 2 0 0 1 -2 -2v-12a2 2 0 0 1 2 -2h12a2 2 0 0 1 2 2v4" />
  <circle cx="18" cy="18" r="4" />
  <path d="M15 3v4" />
  <path d="M7 3v4" />
  <path d="M3 11h16" />
  <path d="M18 16.496v1.504l1 1" />
</svg>
                <time class="article-time--published">Jan 10, 2021</time>
            </div>
        

        
            <div>
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-clock" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="12" cy="12" r="9" />
  <polyline points="12 7 12 12 15 15" />
</svg>



                <time class="article-time--reading">
                    阅读时长: 5 分钟
                </time>
            </div>
        
    </footer>
    
</div>
</header>

    <section class="article-content">
    <p>考前整理的算法，也顺便放到博客上吧ヾ(•ω•`)o</p>
<h2 id="数据结构代码复习">数据结构代码复习</h2>
<h3 id="3单链表逆置">3.单链表逆置</h3>
<p>带头结点</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="kt">int</span> <span class="nf">Inverse_Link</span><span class="p">(</span><span class="n">LinkList</span> <span class="o">*</span><span class="n">L</span><span class="p">)</span>
<span class="p">{</span>
    <span class="n">LinkList</span> <span class="o">*</span><span class="n">cur</span><span class="p">,</span> <span class="o">*</span><span class="n">p</span><span class="p">;</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">L</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">&amp;&amp;</span> <span class="n">L</span><span class="o">-&gt;</span><span class="n">next</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">p</span> <span class="o">=</span> <span class="n">L</span><span class="o">-&gt;</span><span class="n">next</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
        <span class="n">L</span><span class="o">-&gt;</span><span class="n">next</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="nb">NULL</span><span class="p">;</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">p</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">cur</span> <span class="o">=</span> <span class="n">L</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
            <span class="n">L</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="n">p</span><span class="p">;</span>
            <span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
            <span class="n">L</span><span class="o">-&gt;</span><span class="n">next</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="n">cur</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h3 id="5双向链表">5.双向链表</h3>
<p>双链表定义：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="k">typedef</span> <span class="k">struct</span> <span class="n">DuLinkList</span>
<span class="p">{</span>
    <span class="kt">int</span> <span class="n">data</span><span class="p">;</span>
    <span class="k">struct</span> <span class="n">DuLinkList</span> <span class="o">*</span><span class="n">prior</span><span class="p">;</span>
    <span class="k">struct</span> <span class="n">DuLinkList</span> <span class="o">*</span><span class="n">next</span><span class="p">;</span>
<span class="p">}</span> <span class="n">DuLinkList</span><span class="p">;</span>
</code></pre></div><p>遍历：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="kt">void</span> <span class="nf">Printlist_DuL</span><span class="p">(</span><span class="n">DuLinkList</span> <span class="o">*</span><span class="n">L</span><span class="p">)</span>
<span class="p">{</span>
    <span class="n">DuLinkList</span> <span class="o">*</span><span class="n">s</span><span class="p">;</span>
    <span class="n">s</span> <span class="o">=</span> <span class="n">L</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">L</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">printf</span><span class="p">(</span><span class="s">&#34;当前的双向链表值为：&#34;</span><span class="p">);</span>
        <span class="k">do</span>
        <span class="p">{</span>
            <span class="n">printf</span><span class="p">(</span><span class="s">&#34;%d &#34;</span><span class="p">,</span> <span class="n">s</span><span class="o">-&gt;</span><span class="n">data</span><span class="p">);</span>
            <span class="n">s</span> <span class="o">=</span> <span class="n">s</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
        <span class="p">}</span> <span class="k">while</span> <span class="p">(</span><span class="n">s</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="n">printf</span><span class="p">(</span><span class="s">&#34;</span><span class="se">\n</span><span class="s">&#34;</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></div><p>交换：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="kt">int</span> <span class="nf">ListSwap_DuL</span><span class="p">(</span><span class="n">DuLinkList</span> <span class="o">*</span><span class="n">L</span><span class="p">,</span> <span class="kt">int</span> <span class="n">i</span><span class="p">)</span>
<span class="p">{</span>
    <span class="c1">//在带头结点的双向链表中交换第i个，i+1个位置的元素
</span><span class="c1"></span>    <span class="n">DuLinkList</span> <span class="o">*</span><span class="n">p</span> <span class="o">=</span> <span class="n">L</span><span class="p">,</span> <span class="o">*</span><span class="n">q</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">p</span> <span class="o">&amp;&amp;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
        <span class="n">j</span> <span class="o">+=</span> <span class="mi">1</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">p</span> <span class="o">||</span> <span class="n">j</span> <span class="o">&gt;</span> <span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span>
        <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span>
    <span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
    <span class="n">q</span> <span class="o">=</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
    <span class="n">p</span><span class="o">-&gt;</span><span class="n">prior</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="n">q</span><span class="p">;</span>  <span class="c1">//1  -&gt;q    p    2
</span><span class="c1"></span>    <span class="n">q</span><span class="o">-&gt;</span><span class="n">prior</span> <span class="o">=</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">prior</span><span class="p">;</span> <span class="c1">//1&lt;--&gt;q    p    2
</span><span class="c1"></span>    <span class="n">p</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="n">q</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>   <span class="c1">//1&lt;--&gt;q    p  -&gt;2
</span><span class="c1"></span>    <span class="n">q</span><span class="o">-&gt;</span><span class="n">next</span><span class="o">-&gt;</span><span class="n">prior</span> <span class="o">=</span> <span class="n">p</span><span class="p">;</span>  <span class="c1">//1&lt;--&gt;q    p&lt;--&gt;2
</span><span class="c1"></span>    <span class="n">q</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="n">p</span><span class="p">;</span>         <span class="c1">//1&lt;--&gt;q  -&gt;p&lt;--&gt;2
</span><span class="c1"></span>    <span class="n">p</span><span class="o">-&gt;</span><span class="n">prior</span> <span class="o">=</span> <span class="n">q</span><span class="p">;</span>        <span class="c1">//1&lt;--&gt;q&lt;--&gt;p&lt;--&gt;2
</span><span class="c1"></span>    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h3 id="6链表回文">6.链表回文</h3>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-C" data-lang="C"><span class="kt">bool</span> <span class="nf">isPalindrome</span><span class="p">(</span><span class="k">struct</span> <span class="n">ListNode</span> <span class="o">*</span><span class="n">head</span><span class="p">)</span>
<span class="p">{</span>
    <span class="n">Lstack</span> <span class="o">*</span><span class="n">s</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">e</span><span class="p">;</span>
    <span class="k">struct</span> <span class="n">ListNode</span> <span class="o">*</span><span class="n">p</span> <span class="o">=</span> <span class="n">head</span><span class="p">;</span>
    <span class="n">s</span> <span class="o">=</span> <span class="p">(</span><span class="n">Lstack</span> <span class="o">*</span><span class="p">)</span><span class="n">malloc</span><span class="p">(</span><span class="k">sizeof</span><span class="p">(</span><span class="n">Lstack</span><span class="p">));</span>
    <span class="n">Initlist_Stack</span><span class="p">(</span><span class="n">s</span><span class="p">);</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">p</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">push</span><span class="p">(</span><span class="n">s</span><span class="p">,</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">val</span><span class="p">);</span>
        <span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="n">p</span> <span class="o">=</span> <span class="n">head</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">p</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">e</span> <span class="o">=</span> <span class="n">pop</span><span class="p">(</span><span class="n">s</span><span class="p">);</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">val</span> <span class="o">!=</span> <span class="n">e</span><span class="p">)</span>
            <span class="k">break</span><span class="p">;</span>
        <span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">p</span><span class="p">)</span>
        <span class="k">return</span> <span class="nb">false</span><span class="p">;</span>
    <span class="k">else</span>
        <span class="k">return</span> <span class="nb">true</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h3 id="7-1链队列">7-1.链队列</h3>
<p>定义：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="k">typedef</span> <span class="k">struct</span> <span class="n">QNode</span> <span class="c1">//队列
</span><span class="c1"></span><span class="p">{</span>
    <span class="kt">int</span> <span class="n">data</span><span class="p">;</span>
    <span class="k">struct</span> <span class="n">QNode</span> <span class="o">*</span><span class="n">next</span><span class="p">;</span>
<span class="p">}</span> <span class="n">QNode</span><span class="p">;</span>

<span class="k">typedef</span> <span class="k">struct</span> <span class="n">LinkQueue</span> <span class="c1">//对列相关的指针
</span><span class="c1"></span><span class="p">{</span>
    <span class="n">QNode</span> <span class="o">*</span><span class="n">front</span><span class="p">;</span> <span class="c1">//对头指针
</span><span class="c1"></span>    <span class="n">QNode</span> <span class="o">*</span><span class="n">rear</span><span class="p">;</span>  <span class="c1">//队尾指针
</span><span class="c1"></span><span class="p">}</span> <span class="n">LinkQueue</span><span class="p">;</span>
</code></pre></div><p>插入：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="kt">int</span> <span class="nf">EnQueue</span><span class="p">(</span><span class="n">LinkQueue</span> <span class="o">*</span><span class="n">q</span><span class="p">,</span> <span class="kt">int</span> <span class="n">e</span><span class="p">)</span>
<span class="p">{</span>
    <span class="c1">//[入队]将元素e放入队尾，带头结点
</span><span class="c1"></span>    <span class="n">QNode</span> <span class="o">*</span><span class="n">p</span><span class="p">;</span>
    <span class="n">p</span> <span class="o">=</span> <span class="p">(</span><span class="n">QNode</span> <span class="o">*</span><span class="p">)</span><span class="n">malloc</span><span class="p">(</span><span class="k">sizeof</span><span class="p">(</span><span class="n">QNode</span><span class="p">));</span>
    <span class="n">p</span><span class="o">-&gt;</span><span class="n">data</span> <span class="o">=</span> <span class="n">e</span><span class="p">;</span>
    <span class="n">p</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="nb">NULL</span><span class="p">;</span>
    <span class="n">q</span><span class="o">-&gt;</span><span class="n">rear</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="n">p</span><span class="p">;</span>
    <span class="n">q</span><span class="o">-&gt;</span><span class="n">rear</span> <span class="o">=</span> <span class="n">p</span><span class="p">;</span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h3 id="7-2循环链表">7-2.循环链表</h3>
<p>插入和普通单链表没区别，这里就列举部分</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c">    <span class="n">s</span> <span class="o">=</span> <span class="p">(</span><span class="n">LinkList</span> <span class="o">*</span><span class="p">)</span><span class="n">malloc</span><span class="p">(</span><span class="k">sizeof</span><span class="p">(</span><span class="n">LinkList</span><span class="p">));</span>
    <span class="n">s</span><span class="o">-&gt;</span><span class="n">data</span> <span class="o">=</span> <span class="n">e</span><span class="p">;</span>
    <span class="n">s</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">next</span><span class="p">;</span>
    <span class="n">p</span><span class="o">-&gt;</span><span class="n">next</span> <span class="o">=</span> <span class="n">s</span><span class="p">;</span>
</code></pre></div><h3 id="8求二叉树各种数的算法">8.求二叉树各种数的算法</h3>
<h4 id="1求高度">（1）求高度</h4>
<p>高度很简单，来个递归就完事了</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="kt">int</span> <span class="nf">BiTreeHeight</span><span class="p">(</span><span class="n">BiTNode</span> <span class="o">*</span><span class="n">T</span><span class="p">)</span>
<span class="p">{</span>
    <span class="c1">//求二叉树的高度
</span><span class="c1"></span>    <span class="kt">int</span> <span class="n">treeHeight</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">T</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="kt">int</span> <span class="n">leftHeight</span> <span class="o">=</span> <span class="n">BiTreeHeight</span><span class="p">(</span><span class="n">T</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">);</span>
        <span class="kt">int</span> <span class="n">rightHeight</span> <span class="o">=</span> <span class="n">BiTreeHeight</span><span class="p">(</span><span class="n">T</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">);</span>
        <span class="n">treeHeight</span> <span class="o">=</span> <span class="n">leftHeight</span> <span class="o">&gt;=</span> <span class="n">rightHeight</span> <span class="o">?</span> <span class="n">leftHeight</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">:</span> <span class="n">rightHeight</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
    <span class="p">}</span>

    <span class="k">return</span> <span class="n">treeHeight</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h4 id="2求叶子数">（2）求叶子数</h4>
<p>叶子数也一样，递归永远滴神</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="kt">void</span> <span class="nf">BiTreeLeafCount</span><span class="p">(</span><span class="n">BiTNode</span> <span class="o">*</span><span class="n">T</span><span class="p">,</span> <span class="kt">int</span> <span class="o">*</span><span class="n">count</span><span class="p">)</span>
<span class="p">{</span>
    <span class="c1">//求二叉树叶子结点数
</span><span class="c1"></span>    <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">T</span><span class="p">)</span>
        <span class="k">return</span><span class="p">;</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">T</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">==</span> <span class="nb">NULL</span> <span class="o">&amp;&amp;</span> <span class="n">T</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">==</span> <span class="nb">NULL</span><span class="p">)</span>
        <span class="o">*</span><span class="n">count</span> <span class="o">+=</span> <span class="mi">1</span><span class="p">;</span>
    <span class="n">BiTreeLeafCount</span><span class="p">(</span><span class="n">T</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">,</span> <span class="n">count</span><span class="p">);</span>
    <span class="n">BiTreeLeafCount</span><span class="p">(</span><span class="n">T</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">,</span> <span class="n">count</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></div><h4 id="3求结点数">（3）求结点数</h4>
<p>这不就遍历嘛，直接看下面吧=￣ω￣=</p>
<h3 id="9二叉树的中序遍历">9.二叉树的中序遍历</h3>
<p>递归：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="kt">int</span> <span class="nf">InOrderTraverse</span><span class="p">(</span><span class="n">BiTNode</span> <span class="o">*</span><span class="n">T</span><span class="p">)</span>
<span class="p">{</span>
    <span class="c1">//中序遍历二叉树T的递归算法
</span><span class="c1"></span>    <span class="k">if</span> <span class="p">(</span><span class="n">T</span> <span class="o">==</span> <span class="nb">NULL</span><span class="p">)</span>
        <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
    <span class="n">InOrderTraverse</span><span class="p">(</span><span class="n">T</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">);</span>
    <span class="n">printf</span><span class="p">(</span><span class="s">&#34;%c &#34;</span><span class="p">,</span> <span class="n">T</span><span class="o">-&gt;</span><span class="n">data</span><span class="p">);</span>
    <span class="n">InOrderTraverse</span><span class="p">(</span><span class="n">T</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></div><p>非递归（重要）：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="kt">int</span> <span class="nf">inorder</span><span class="p">(</span><span class="n">BiTNode</span> <span class="o">*</span><span class="n">T</span><span class="p">)</span>
<span class="p">{</span>
    <span class="c1">//中序遍历二叉树T的非递归算法
</span><span class="c1"></span>    <span class="n">BiTNode</span> <span class="o">*</span><span class="n">s</span><span class="p">[</span><span class="n">MAXSIZE</span> <span class="o">+</span> <span class="mi">1</span><span class="p">];</span>
    <span class="kt">int</span> <span class="n">top</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">T</span> <span class="o">!=</span> <span class="nb">NULL</span> <span class="o">||</span> <span class="n">top</span> <span class="o">!=</span> <span class="mi">0</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">T</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">s</span><span class="p">[</span><span class="o">++</span><span class="n">top</span><span class="p">]</span> <span class="o">=</span> <span class="n">T</span><span class="p">;</span>
            <span class="n">T</span> <span class="o">=</span> <span class="n">T</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">top</span> <span class="o">!=</span> <span class="mi">0</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">T</span> <span class="o">=</span> <span class="n">s</span><span class="p">[</span><span class="n">top</span><span class="o">--</span><span class="p">];</span>
            <span class="n">printf</span><span class="p">(</span><span class="s">&#34;%c &#34;</span><span class="p">,</span> <span class="n">T</span><span class="o">-&gt;</span><span class="n">data</span><span class="p">);</span>
            <span class="n">T</span> <span class="o">=</span> <span class="n">T</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h3 id="10二叉排序树">10.二叉排序树</h3>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="kt">int</span> <span class="nf">Search_BST</span><span class="p">(</span><span class="n">BSTree</span> <span class="n">t</span><span class="p">,</span> <span class="kt">int</span> <span class="n">key</span><span class="p">,</span> <span class="n">BSTree</span> <span class="n">f</span><span class="p">,</span> <span class="n">BSTree</span> <span class="o">*</span><span class="n">p</span><span class="p">)</span>
<span class="p">{</span>
    <span class="c1">//在指针t所指的二叉排序树上查找key，成功则p指向该元素数据结点并返回0
</span><span class="c1"></span>    <span class="c1">//否则p指向查找路径上最后一个结点并返回1，f指向T的双亲，初始值为NULL
</span><span class="c1"></span>    <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">t</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="o">*</span><span class="n">p</span> <span class="o">=</span> <span class="n">f</span><span class="p">;</span>
        <span class="k">return</span> <span class="mi">1</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="n">key</span> <span class="o">==</span> <span class="n">t</span><span class="o">-&gt;</span><span class="n">data</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="o">*</span><span class="n">p</span> <span class="o">=</span> <span class="n">t</span><span class="p">;</span>
        <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="n">key</span> <span class="o">&lt;</span> <span class="n">t</span><span class="o">-&gt;</span><span class="n">data</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="k">return</span> <span class="n">Search_BST</span><span class="p">(</span><span class="n">t</span><span class="o">-&gt;</span><span class="n">lchild</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">t</span><span class="p">,</span> <span class="n">p</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="k">else</span>
        <span class="k">return</span> <span class="n">Search_BST</span><span class="p">(</span><span class="n">t</span><span class="o">-&gt;</span><span class="n">rchild</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">t</span><span class="p">,</span> <span class="n">p</span><span class="p">);</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="nf">Insert_BST</span><span class="p">(</span><span class="n">BSTree</span> <span class="o">*</span><span class="n">t</span><span class="p">,</span> <span class="kt">int</span> <span class="n">key</span><span class="p">)</span>
<span class="p">{</span> <span class="c1">//二叉排序树的插入，当不存在key时插入并返回0，否则返回1
</span><span class="c1"></span>    <span class="n">BSTree</span> <span class="n">p</span><span class="p">,</span> <span class="n">s</span><span class="p">;</span>
    <span class="n">p</span> <span class="o">=</span> <span class="nb">NULL</span><span class="p">;</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">Search_BST</span><span class="p">(</span><span class="o">*</span><span class="n">t</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="nb">NULL</span><span class="p">,</span> <span class="o">&amp;</span><span class="n">p</span><span class="p">))</span>
    <span class="p">{</span>
        <span class="n">s</span> <span class="o">=</span> <span class="p">(</span><span class="n">BSTree</span><span class="p">)</span><span class="n">malloc</span><span class="p">(</span><span class="k">sizeof</span><span class="p">(</span><span class="n">BSTNode</span><span class="p">));</span>
        <span class="n">s</span><span class="o">-&gt;</span><span class="n">data</span> <span class="o">=</span> <span class="n">key</span><span class="p">;</span>
        <span class="n">s</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">s</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="nb">NULL</span><span class="p">;</span>
        <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">p</span><span class="p">)</span>
            <span class="o">*</span><span class="n">t</span> <span class="o">=</span> <span class="n">s</span><span class="p">;</span>
        <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="n">key</span> <span class="o">&lt;</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">data</span><span class="p">)</span>
            <span class="n">p</span><span class="o">-&gt;</span><span class="n">lchild</span> <span class="o">=</span> <span class="n">s</span><span class="p">;</span>
        <span class="k">else</span>
            <span class="n">p</span><span class="o">-&gt;</span><span class="n">rchild</span> <span class="o">=</span> <span class="n">s</span><span class="p">;</span>
        <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">else</span>
        <span class="k">return</span> <span class="mi">1</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h3 id="14图的遍历">14.图的遍历</h3>
<h4 id="1深度优先">（1）深度优先</h4>
<p>入栈时打印结点信息</p>
<p>递归：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="kt">void</span> <span class="nf">DFS</span><span class="p">(</span><span class="n">ALGraph</span> <span class="o">*</span><span class="n">G</span><span class="p">,</span> <span class="kt">int</span> <span class="n">v</span><span class="p">,</span> <span class="kt">int</span> <span class="n">visited</span><span class="p">[])</span>
<span class="p">{</span>
    <span class="n">ArcNode</span> <span class="o">*</span><span class="n">p</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">w</span><span class="p">,</span> <span class="n">i</span><span class="p">;</span>
    <span class="n">visited</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
    <span class="n">printf</span><span class="p">(</span><span class="s">&#34;%d &#34;</span><span class="p">,</span> <span class="n">v</span><span class="p">);</span>
    <span class="n">p</span> <span class="o">=</span> <span class="n">G</span><span class="o">-&gt;</span><span class="n">vertices</span><span class="p">[</span><span class="n">v</span><span class="p">].</span><span class="n">firstarc</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">p</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">w</span> <span class="o">=</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">adjvex</span><span class="p">;</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">visited</span><span class="p">[</span><span class="n">w</span><span class="p">]</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span>
            <span class="n">DFS</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">w</span><span class="p">,</span> <span class="n">visited</span><span class="p">);</span>
        <span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">nextarc</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">}</span>
</code></pre></div><p>非递归：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="kt">void</span> <span class="nf">DFS1</span><span class="p">(</span><span class="n">ALGraph</span> <span class="o">*</span><span class="n">G</span><span class="p">,</span> <span class="kt">int</span> <span class="n">v</span><span class="p">)</span>
<span class="p">{</span>
    <span class="n">ArcNode</span> <span class="o">*</span><span class="n">p</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">w</span><span class="p">,</span> <span class="n">i</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">visited</span><span class="p">[</span><span class="n">MAX_VERTEX_NUM</span><span class="p">];</span>
    <span class="n">ArcNode</span> <span class="o">*</span><span class="n">s</span><span class="p">[</span><span class="n">MAX_VERTEX_NUM</span><span class="p">];</span> <span class="c1">//顺序栈
</span><span class="c1"></span>    <span class="kt">int</span> <span class="n">top</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
    <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">G</span><span class="o">-&gt;</span><span class="n">vexnum</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
        <span class="n">visited</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="c1">//访问标志数组初始化
</span><span class="c1"></span>    <span class="n">visited</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
    <span class="n">printf</span><span class="p">(</span><span class="s">&#34;%2d&#34;</span><span class="p">,</span> <span class="n">v</span><span class="p">);</span>
    <span class="n">p</span> <span class="o">=</span> <span class="n">G</span><span class="o">-&gt;</span><span class="n">vertices</span><span class="p">[</span><span class="n">v</span><span class="p">].</span><span class="n">firstarc</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">p</span> <span class="o">!=</span> <span class="nb">NULL</span> <span class="o">||</span> <span class="n">top</span> <span class="o">!=</span> <span class="mi">0</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="k">while</span> <span class="p">(</span><span class="n">p</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">w</span> <span class="o">=</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">adjvex</span><span class="p">;</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">visited</span><span class="p">[</span><span class="n">w</span><span class="p">]</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span>
            <span class="p">{</span>
                <span class="n">printf</span><span class="p">(</span><span class="s">&#34;%2d&#34;</span><span class="p">,</span> <span class="n">w</span><span class="p">);</span>
                <span class="n">visited</span><span class="p">[</span><span class="n">w</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
                <span class="n">s</span><span class="p">[</span><span class="o">++</span><span class="n">top</span><span class="p">]</span> <span class="o">=</span> <span class="n">p</span><span class="p">;</span>
                <span class="n">p</span> <span class="o">=</span> <span class="n">G</span><span class="o">-&gt;</span><span class="n">vertices</span><span class="p">[</span><span class="n">w</span><span class="p">].</span><span class="n">firstarc</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="k">else</span>
                <span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">nextarc</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">top</span> <span class="o">!=</span> <span class="mi">0</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">p</span> <span class="o">=</span> <span class="n">s</span><span class="p">[</span><span class="n">top</span><span class="o">--</span><span class="p">];</span>
            <span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">nextarc</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
<span class="p">}</span>
</code></pre></div><h4 id="2广度优先">（2）广度优先</h4>
<p>出队列时打印结点信息</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="kt">void</span> <span class="nf">BFS</span><span class="p">(</span><span class="n">ALGraph</span> <span class="o">*</span><span class="n">G</span><span class="p">,</span> <span class="kt">int</span> <span class="n">v</span><span class="p">)</span>
<span class="p">{</span>
    <span class="n">ArcNode</span> <span class="o">*</span><span class="n">p</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">w</span><span class="p">,</span> <span class="n">i</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">queue</span><span class="p">[</span><span class="n">MAX_VERTEX_NUM</span><span class="p">],</span> <span class="n">front</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">rear</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="c1">// 定义循环队列
</span><span class="c1"></span>    <span class="kt">int</span> <span class="n">visited</span><span class="p">[</span><span class="n">MAX_VERTEX_NUM</span><span class="p">];</span>
    <span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;=</span> <span class="n">G</span><span class="o">-&gt;</span><span class="n">vexnum</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
        <span class="n">visited</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="c1">//访问标志数组初始化
</span><span class="c1"></span>    <span class="n">printf</span><span class="p">(</span><span class="s">&#34;%2d&#34;</span><span class="p">,</span> <span class="n">v</span><span class="p">);</span>   <span class="c1">//输出被访问顶点的编号
</span><span class="c1"></span>    <span class="n">visited</span><span class="p">[</span><span class="n">v</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>     <span class="c1">//置已访问标记
</span><span class="c1"></span>    <span class="n">rear</span> <span class="o">=</span> <span class="p">(</span><span class="n">rear</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="o">%</span> <span class="n">MAX_VERTEX_NUM</span><span class="p">;</span>
    <span class="n">queue</span><span class="p">[</span><span class="n">rear</span><span class="p">]</span> <span class="o">=</span> <span class="n">v</span><span class="p">;</span>      <span class="c1">//v进队
</span><span class="c1"></span>    <span class="k">while</span> <span class="p">(</span><span class="n">front</span> <span class="o">!=</span> <span class="n">rear</span><span class="p">)</span> <span class="c1">// 队列不空时循环
</span><span class="c1"></span>    <span class="p">{</span>
        <span class="n">front</span> <span class="o">=</span> <span class="p">(</span><span class="n">front</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="o">%</span> <span class="n">MAX_VERTEX_NUM</span><span class="p">;</span>
        <span class="n">w</span> <span class="o">=</span> <span class="n">queue</span><span class="p">[</span><span class="n">front</span><span class="p">];</span>            <span class="c1">//出队并赋给w
</span><span class="c1"></span>        <span class="n">p</span> <span class="o">=</span> <span class="n">G</span><span class="o">-&gt;</span><span class="n">vertices</span><span class="p">[</span><span class="n">w</span><span class="p">].</span><span class="n">firstarc</span><span class="p">;</span> <span class="c1">//找w的第一个的邻接点
</span><span class="c1"></span>        <span class="k">while</span> <span class="p">(</span><span class="n">p</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">visited</span><span class="p">[</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">adjvex</span><span class="p">]</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span>
            <span class="p">{</span>
                <span class="n">printf</span><span class="p">(</span><span class="s">&#34;%2d&#34;</span><span class="p">,</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">adjvex</span><span class="p">);</span> <span class="c1">//访问之
</span><span class="c1"></span>                <span class="n">visited</span><span class="p">[</span><span class="n">p</span><span class="o">-&gt;</span><span class="n">adjvex</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
                <span class="n">rear</span> <span class="o">=</span> <span class="p">(</span><span class="n">rear</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="o">%</span> <span class="n">MAX_VERTEX_NUM</span><span class="p">;</span> <span class="c1">//相邻顶点进队
</span><span class="c1"></span>                <span class="n">queue</span><span class="p">[</span><span class="n">rear</span><span class="p">]</span> <span class="o">=</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">adjvex</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="n">p</span> <span class="o">=</span> <span class="n">p</span><span class="o">-&gt;</span><span class="n">nextarc</span><span class="p">;</span> <span class="c1">//找下一个邻接顶点
</span><span class="c1"></span>        <span class="p">}</span>
    <span class="p">}</span>
<span class="p">}</span>
</code></pre></div><h3 id="15双向冒泡">15.双向冒泡</h3>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c" data-lang="c"><span class="kt">void</span> <span class="nf">BubbleSort1</span><span class="p">(</span><span class="kt">int</span> <span class="n">R</span><span class="p">[],</span> <span class="kt">int</span> <span class="n">n</span><span class="p">)</span>
<span class="p">{</span> <span class="c1">//双向冒泡
</span><span class="c1"></span>    <span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="n">j</span><span class="p">,</span> <span class="n">lastExchange</span><span class="p">,</span> <span class="n">lastExchange1</span><span class="p">,</span> <span class="n">i1</span><span class="p">,</span> <span class="n">temp</span><span class="p">;</span>
    <span class="n">i</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span> <span class="c1">//i 指示无序序列中最后一个记录的位置
</span><span class="c1"></span>    <span class="n">i1</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">i</span> <span class="o">&gt;</span> <span class="n">i1</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">lastExchange</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>  <span class="c1">//记录正序最后一次交换发生的位置
</span><span class="c1"></span>        <span class="n">lastExchange1</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span> <span class="c1">//记录逆序最后一次交换发生的位置
</span><span class="c1"></span>        <span class="k">for</span> <span class="p">(</span><span class="n">j</span> <span class="o">=</span> <span class="n">i1</span><span class="p">;</span> <span class="n">j</span> <span class="o">&lt;</span> <span class="n">i</span><span class="p">;</span> <span class="n">j</span><span class="o">++</span><span class="p">)</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">R</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">R</span><span class="p">[</span><span class="n">j</span> <span class="o">+</span> <span class="mi">1</span><span class="p">])</span>
            <span class="p">{</span>
                <span class="n">temp</span> <span class="o">=</span> <span class="n">R</span><span class="p">[</span><span class="n">j</span><span class="p">];</span>
                <span class="n">R</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">R</span><span class="p">[</span><span class="n">j</span> <span class="o">+</span> <span class="mi">1</span><span class="p">];</span>
                <span class="n">R</span><span class="p">[</span><span class="n">j</span> <span class="o">+</span> <span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="n">temp</span><span class="p">;</span> <span class="c1">//逆序时交换
</span><span class="c1"></span>                <span class="n">lastExchange</span> <span class="o">=</span> <span class="n">j</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="k">for</span> <span class="p">(</span><span class="n">j</span> <span class="o">=</span> <span class="n">lastExchange</span><span class="p">;</span> <span class="n">j</span> <span class="o">&gt;</span> <span class="n">i1</span><span class="p">;</span> <span class="n">j</span><span class="o">--</span><span class="p">)</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">R</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">R</span><span class="p">[</span><span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="p">])</span>
            <span class="p">{</span>
                <span class="n">temp</span> <span class="o">=</span> <span class="n">R</span><span class="p">[</span><span class="n">j</span><span class="p">];</span>
                <span class="n">R</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="n">R</span><span class="p">[</span><span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="p">];</span>
                <span class="n">R</span><span class="p">[</span><span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="n">temp</span><span class="p">;</span> <span class="c1">//逆序时交换
</span><span class="c1"></span>                <span class="n">lastExchange1</span> <span class="o">=</span> <span class="n">j</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="n">i</span> <span class="o">=</span> <span class="n">lastExchange</span><span class="p">;</span>
        <span class="n">i1</span> <span class="o">=</span> <span class="n">lastExchange1</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">}</span>
</code></pre></div>
</section>


    <footer class="article-footer">
    
    <section class="article-tags">
        
            <a href="/tags/c/">C</a>
        
    </section>


    
    <section class="article-copyright">
        <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-copyright" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="12" cy="12" r="9" />
  <path d="M14.5 9a3.5 4 0 1 0 0 6" />
</svg>



        <span>Licensed under CC BY-NC-SA 4.0</span>
    </section>
    <section class="article-time">
        <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-clock" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="12" cy="12" r="9" />
  <polyline points="12 7 12 12 15 15" />
</svg>



        <span class="article-time--modified">
            最后更新于 Jan 13, 2021 20:47 &#43;0800
        </span>
    </section></footer>


    
</article>

    <aside class="related-contents--wrapper">
    
    
</aside>

     
     
        
    

    <footer class="site-footer">
    <section class="copyright">
        &copy; 
        
            2020 - 
        
        2021 luoboQAQ
    </section>
    
    <section class="powerby">
        Built with <a href="https://gohugo.io/" target="_blank" rel="noopener">Hugo</a> <br />
        Theme <b><a href="https://github.com/CaiJimmy/hugo-theme-stack" target="_blank" rel="noopener" data-version="3.0.0">Stack</a></b> designed by <a href="https://jimmycai.com" target="_blank" rel="noopener">Jimmy</a>
    </section>
</footer>

    
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

    
    <div class="pswp__bg"></div>

    
    <div class="pswp__scroll-wrap">

        
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>

        
        <div class="pswp__ui pswp__ui--hidden">

            <div class="pswp__top-bar">

                

                <div class="pswp__counter"></div>

                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>

                <button class="pswp__button pswp__button--share" title="Share"></button>

                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>

                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>

                
                
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                        <div class="pswp__preloader__cut">
                            <div class="pswp__preloader__donut"></div>
                        </div>
                    </div>
                </div>
            </div>

            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div>
            </div>

            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>

            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>

            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>

        </div>

    </div>

</div><script 
                src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.js"integrity="sha256-ePwmChbbvXbsO02lbM3HoHbSHTHFAeChekF1xKJdleo="crossorigin="anonymous"
                defer="true"
                >
            </script><script 
                src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe-ui-default.min.js"integrity="sha256-UKkzOn/w1mBxRmLLGrSeyB4e1xbrp4xylgAWb3M42pU="crossorigin="anonymous"
                defer="true"
                >
            </script><link 
                rel="stylesheet" 
                href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/default-skin/default-skin.css"integrity="sha256-c0uckgykQ9v5k&#43;IqViZOZKc47Jn7KQil4/MP3ySA3F8="crossorigin="anonymous"
            ><link 
                rel="stylesheet" 
                href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.css"integrity="sha256-SBLU4vv6CA6lHsZ1XyTdhyjJxCjPif/TRkjnsyGAGnE="crossorigin="anonymous"
            >

            </main>
    
        <aside class="sidebar right-sidebar sticky">
            <section class="widget archives">
                <div class="widget-icon">
                    <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-hash" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <line x1="5" y1="9" x2="19" y2="9" />
  <line x1="5" y1="15" x2="19" y2="15" />
  <line x1="11" y1="4" x2="7" y2="20" />
  <line x1="17" y1="4" x2="13" y2="20" />
</svg>



                </div>
                <h2 class="widget-title section-title">目录</h2>
                
                <div class="widget--toc">
                    <nav id="TableOfContents">
  <ol>
    <li><a href="#数据结构代码复习">数据结构代码复习</a>
      <ol>
        <li><a href="#3单链表逆置">3.单链表逆置</a></li>
        <li><a href="#5双向链表">5.双向链表</a></li>
        <li><a href="#6链表回文">6.链表回文</a></li>
        <li><a href="#7-1链队列">7-1.链队列</a></li>
        <li><a href="#7-2循环链表">7-2.循环链表</a></li>
        <li><a href="#8求二叉树各种数的算法">8.求二叉树各种数的算法</a>
          <ol>
            <li><a href="#1求高度">（1）求高度</a></li>
            <li><a href="#2求叶子数">（2）求叶子数</a></li>
            <li><a href="#3求结点数">（3）求结点数</a></li>
          </ol>
        </li>
        <li><a href="#9二叉树的中序遍历">9.二叉树的中序遍历</a></li>
        <li><a href="#10二叉排序树">10.二叉排序树</a></li>
        <li><a href="#14图的遍历">14.图的遍历</a>
          <ol>
            <li><a href="#1深度优先">（1）深度优先</a></li>
            <li><a href="#2广度优先">（2）广度优先</a></li>
          </ol>
        </li>
        <li><a href="#15双向冒泡">15.双向冒泡</a></li>
      </ol>
    </li>
  </ol>
</nav>
                </div>
            </section>
        </aside>
    

        </div>
        <script 
                src="https://cdn.jsdelivr.net/npm/node-vibrant@3.1.5/dist/vibrant.min.js"integrity="sha256-5NovOZc4iwiAWTYIFiIM7DxKUXKWvpVEuMEPLzcm5/g="crossorigin="anonymous"
                defer="false"
                >
            </script><script type="text/javascript" src="/ts/main.js" defer></script>
<script>
    (function () {
        const customFont = document.createElement('link');
        customFont.href = "https://fonts.googleapis.com/css2?family=Lato:wght@300;400;700&display=swap";

        customFont.type = "text/css";
        customFont.rel = "stylesheet";

        document.head.appendChild(customFont);
    }());
</script>

    </body>
</html>
